package com.wenhai.mj.tree;

import com.wenhai.mj.printer.BinaryTreeInfo;

import java.util.Comparator;
import java.util.LinkedList;
import java.util.Queue;
import java.util.function.Consumer;

/**
 * 二叉搜索树
 *
 * @author wenhai
 * @date   2021/1/16
 */
@SuppressWarnings("unchecked")
public class BinarySearchTree<E> implements BinaryTreeInfo {
    private int           size;
    private Node<E>       root;
    private Comparator<E> comparator;

    public BinarySearchTree() {
    }

    public BinarySearchTree(Comparator<E> comparator) {
        this.comparator = comparator;
    }

    public int size() {
        return this.size;
    }

    public boolean isEmpty() {
        return this.size == 0;
    }

    public void clear() {
        this.root = null;
        this.size = 0;
    }

    public boolean remove(E e) {
        return remove(node(e));
    }

    private Node<E> node(E e) {
        if (e == null) {
            throw new IllegalArgumentException("Element must be not null");
        }
        if (this.root == null) {
            throw new IllegalStateException("Tree is empty,Please init tree");
        }
        Node<E> node = this.root;
        while (node != null) {
            int cmp = compare(e, node.element);
            if (cmp == 0) {
                return node;
            } else if (cmp > 0) {
                node = node.right;
            } else {
                node = node.left;
            }
        }
        return null;
    }

    private boolean remove(Node<E> node){

        if (node == null) {
            return false;
        }

        // 度为 2 的节点找后继节点,
        if (node.hasTwoChild()) {
            Node<E> successor = successor(node);
            node.element = successor.element;
            node = successor;
        }

        // 度为 1 或者为 0
        Node<E> replacement = node.left != null ? node.left : node.right;

//        if (replacement != null) {
//            replacement.parent = node.parent;
//            if (node.parent == null) {
//                this.root = replacement;
//            } else if (node.parent.right == node) {
//                node.parent.right  = replacement;
//            } else {
//                node.parent.left   = replacement;
//            }
//        } else {
//            if (node.parent == null) {
//                this.root = null;
//            } else if (node.parent.right == node) {
//                node.parent.right  = null;
//            } else {
//                node.parent.left   = null;
//            }
//        }

        if (replacement != null) {
            replacement.parent = node.parent;
        }
        if (node.parent == null) {
            this.root = replacement;
        } else if (node.parent.right == node) {
            node.parent.right = replacement;
        } else {
            node.parent.left = replacement;
        }
        size--;
        return true;
    }


    public boolean contains(E e) {
        return this.node(e) != null;

    }



    public boolean add(E e) {
        this.size++;
        if (this.root == null) {
            this.root = createNode(null, e);
            return true;
        }
        Node<E> parent = this.root;
        Node<E> node   = parent;
        int     cmp    = 0;
        while (node != null) {
            parent = node;
            cmp    = compare(e, node.element);
            if (cmp > 0) {
                node = node.right;
            } else if (cmp < 0) {
                node = node.left;
            } else {
                node.element = e;
                return true;
            }
        }
        node = createNode(parent, e);
        if (cmp > 0) {
            parent.right = node;
        }

        if (cmp < 0) {
            parent.left = node;
        }
        afterAdd(node);
        return true;
    }

    protected void afterAdd(Node<E> node) {
    }

    /**
     * 前序遍历
     */
    public void preorderTraversal(Consumer<E> consumer) {
        preorderTraversal(this.root, consumer);
    }

    /**
     * 中序遍历
     */
    public void inorderTraversal() {
        inorderTraversal(this.root);
    }

    /**
     * 后序遍历
     */
    public void postorderTraversal() {
        postorderTraversal(this.root);
        System.out.println();
    }

    /**
     * 层级遍历 采用队列的思想
     */
    @SuppressWarnings("ConstantConditions")
    public void levelOrderTraversal() {
        if (root == null) {
            return;
        }
        Queue<Node> queue = new LinkedList<>();
        queue.offer(this.root);
        while (!queue.isEmpty()) {
            Node node = queue.poll();
            System.out.print(node.element + " ");
            if (node.left != null) {
                queue.offer(node.left);
            }
            if (node.right != null) {
                queue.offer(node.right);
            }
        }
    }

    /**
     * 高度 采用递归
     * @return 高度
     */
    public int height() {
        return height(this.root);
    }

    private int height(Node<E> node) {
        if (node == null) {
            return 0;
        }
        return 1 + Math.max(height(node.left), height(node.right));
    }

    /**
     * 高度 队列高度
     * @return 高度
     */
    public int heightQueue() {
        int height = 0;
        if (root == null) {
            return height;
        }
        int levelSize  = 1;
        Queue<Node> queue = new LinkedList<>();
        queue.offer(this.root);
        while (!queue.isEmpty()) {
            Node node = queue.poll();
            levelSize -- ;
            if (node.left != null) {
                queue.offer(node.left);
            }
            if (node.right != null) {
                queue.offer(node.right);
            }
            if(levelSize == 0){
                levelSize = queue.size();
                height++;
            }
        }
        return height;
    }

    /**
     * 判断是否是完全二叉树
     *
     * @return true 是
     */
    public boolean isComplete() {

        if (this.root == null) {
            return false;
        }

        boolean isLeaf = false;
        Queue<Node> queue = new LinkedList<>();
        queue.offer(this.root);

        while (!queue.isEmpty()) {
            Node<E> node = queue.poll();
            if (isLeaf && !node.isLeaf()) {
                return false;
            }
            if (node.hasTwoChild()) {
                queue.offer(node.left);
                queue.offer(node.right);
            } else if (node.left == null && node.right != null) {
                return false;
            } else {
                if (node.left != null) {
                    queue.offer(node.left);
                }
                isLeaf = true;
            }
        }
        return true;
    }


    private void postorderTraversal(Node<E> node) {
        if (node == null) {
            return;
        }
        postorderTraversal(node.left);
        postorderTraversal(node.right);
        System.out.print(node.element + " ");
    }

    private void inorderTraversal(Node<E> node) {
        if (node == null) {
            return;
        }
        inorderTraversal(node.left);
        System.out.print(node.element + " ");
        inorderTraversal(node.right);
    }

    private void preorderTraversal(Node<E> node, Consumer<E> consumer) {
        if (node == null) {
            return;
        }
        consumer.accept(node.element);
        preorderTraversal(node.left, consumer);
        preorderTraversal(node.right, consumer);
    }

    private int compare(E e1, E e2) {
        if (comparator != null) {
            return comparator.compare(e1, e2);
        }
        //noinspection unchecked
        return ((Comparable) e1).compareTo(e2);
    }

    /**
     * 前驱节点：中序遍历时的前一个节点
     *
     * @param node 要找节点的前驱节点
     * @return 前驱节点
     */
    private Node<E> predecessor(Node<E> node) {
        if (node == null) {
            return node;
        }
        // node.left.right.right
        Node<E> predecessor = node.left;
        if (predecessor != null) {
            while (predecessor.right != null) {
                predecessor = predecessor.right;
            }
            return predecessor;
        }
        // node.parent.parent ==> node == parent.right
        while (node.parent != null && node == node.parent.left) {
            node = node.parent;
        }
        return node.parent;
    }

    /**
     * 后续节点：中序遍历时的后一个节点
     * @param node 要找后续节点
     * @return 后继节点
     */
    private Node<E> successor(Node<E> node) {
        if (node == null) {
            return node;
        }
        Node<E> successor = node.right;
        if (successor != null) {
            while (successor.left != null) {
                successor = successor.left;
            }
            return successor;
        }

        while (node.parent != null & node == node.parent.right) {
            node = node.parent;
        }
        return node.parent;
    }

    /**
     * who is the root node
     */
    @Override
    public Object root() {
        return this.root;
    }

    /**
     * how to get the left child of the node
     *
     * @param node
     */
    @Override
    public Object left(Object node) {
        return ((Node) node).left;
    }

    /**
     * how to get the right child of the node
     *
     * @param node
     */
    @Override
    public Object right(Object node) {
        return ((Node) node).right;
    }

    /**
     * how to print the node
     *
     * @param node
     */
    @Override
    public Object string(Object node) {
        Node n = (Node) node;
        return n.element + "_p(" + (n.parent == null ? null : n.parent.element) + ")";
    }


    static class Node<E> {
        Node<E> parent;
        E       element;
        Node<E> left;
        Node<E> right;

        Node(Node<E> parent, E element) {
            this.parent  = parent;
            this.element = element;
        }

        boolean hasTwoChild() {
            return this.left != null && this.right != null;
        }

        boolean isLeaf() {
            return this.left == null && this.right == null;
        }

    }


    protected Node<E> createNode(Node<E> parent, E element) {
        return new Node<>(parent, element);
    }
}
